In digital data transmission systems, it is desired to be able to detect and correct bit errors introduced during transmission, preferably without requiring retransmission of the erroneous data. Known error correction systems generate at the transmitter a codeword which comprises some form of redundant, or "overhead," check bits in addition to the transmitted information. Calculations are performed at the receiver using the received codeword to extrapolate the information, and if errors are detected, to correct the data. The factors that can be traded off against each other and still provide effective error correction are the additional bandwidth and time required for transmission; the amount of time needed to perform the calculations; and the complexity and cost of the equipment.
In channel coding theory, a systematic code is defined as a code in which redundant parity check bits are concatenated with information data bits to form a codeword. That is, the information bits form a discrete, identifiable part of the transmitted codeword. A forward error correction (FEC) or detection code has r parity check bits, added to k information data bits to form a codeword of length n such that n=k+r. The r parity check bits are added in such a way as to allow a specified number of errors to be detected and/or corrected. The algorithm employed to generate the r parity-check bits for given information bits differs for each code.
Specific forward error correction and detection codes which are well known in the prior art include the Reed-Solomon code, the Golay code, the Bose-Chadhuri-Hocquenghem (BCH) code and the Hamming code. Each of these codes employs a different algorithm for generating the parity check bits and a correspondingly different algorithm for recovering the original k data bits or for detecting errors.
The forward error correction and detection codes are characterized by their algorithm for encoding and decoding and also by several other properties. The efficiency rate R is the ratio of information data bits k to the sum n of information data bits. The larger the number of information bits k contained in a given codeword of n total bits, the more efficient the codeword is. That is, the efficiency rate R=k/n.
The minimum Hamming distance, or code weight, d is the minimum number of bits by which two codewords differ. If there are k information bits in an uncoded word, there are 2.sup.k possible uncoded information words (e.g., if k=4 there are 16 possible uncoded words). An error in any bit will make the word look like a different one of the 2.sup.4 words, and therefore an error cannot be correctly detected or corrected. However, if r parity check bits are added to the k-bit uncoded word, an n-bit codeword is formed. Hence, there are 2.sup.n possible words of which only 2.sup.k are used as valid information words. The selection of the codewords so as to ensure a maximum separation between the codewords is what makes a good error correcting code. For example, a Hamming code containing k=4 information bits and n=7 coded bits has 16 valid codewords of a possible 2.sup.7 =128 words. This is called a (n,k) or (7,4) code of efficiency rate R=4/7. These codewords are selected so that each codeword differs by 3 bits. Thus, a single error can be detected and corrected while two errors on a codeword can be detected but cannot be corrected. In the above example, the Hamming distance d=3. In general, a code can detect d.sub.min -1 errors in a codeword and can correct t errors in a codeword, where EQU t.ltoreq.(d.sub.min -1)/2
Coding schemes are typically designed into communication systems to provide coding gain that results in an improved link Bit Error Rate (BER). If the modulation and channel bandwidth are fixed, and it is necessary to increase the information rate (or the channel coding efficiency), a commonly selected alterative is to choose another coding scheme with an increased coding efficiency and usually a reduced error correction capability.
In general, block codes are more efficient the larger the block size. However, as a practical matter, the block size often cannot be increased although it is desired to increase the efficiency. Although for a given block size n, the number of information bits k could be increased to increase the efficiency, this has resulted in the prior art in a significantly reduced error detection and correction capability since the number of check bits available is reduced accordingly.
For example, the systematic BCH code for a fixed number of total codeword bits n exhibits an increased efficiency as the number of information bits k increases, but also exhibits an undesirable decreased error correction capability t since the number of redundant parity check bits r decreases, as shown in Table 1 below:
TABLE 1 ______________________________________ BCH Code Characteristics n k r efficiency t ______________________________________ 15 5 10 .33 3 7 8 .47 2 11 5 .73 1 63 24 39 .38 7 36 27 .57 5 39 24 .62 4 45 18 .71 3 51 12 .81 2 57 6 .90 1 255 63 192 .25 30 115 140 .45 21 179 76 .70 10 199 56 .78 7 215 40 .84 5 223 32 .87 4 231 24 .91 3 239 16 .94 2 ______________________________________
It is therefore an object of the present invention to increase the channel coding efficiency for existing systematic block data transmission codes without increasing the codeword length and without substantially reducing the error detection and correction capability.